package algorithm.fft;
/*
 *        [0 1 2 3 4 5 6 7]
 *     [0 2 4 6]        [1 3 5 7]
 *    [0 4]   [2 6]    [1 5]   [3 7]
 *   [0] [4 1] [2] [6]  [1] [5] [3] [7]
 *   
 *   apply bit reversal
 *
 *        [0 1 2 3 4 5 6 7]
 *     [0 1 2 3]        [4 5 6 7]
 *    [0 1]   [2 3]    [4 5]   [6 7]
 *   [0] [1] [2] [3]  [4] [5] [6] [7]  
 *   
 */
public class FFTNode {
	public static final short Node_ROOT=1; 
	public static final short Node_LEFT=2;
	public static final short Node_RIGHT=3;
	public static final int MIN_SIZE=8; 
	
	public int from; 
	public int step; // should be 2^n;
	public int to; 
	public int size; 
	protected boolean isReady=false;
	protected FFTNode parent;
	protected short nodeType;
	private  int order;
	
	private final IFFTNodeFactory f;
	private final WorkMemory wm;
	private Trigonometry t; 
	
	public FFTNode prev; 
	
	public FFTNode preceeding; 
	
		
	public FFTNode(IFFTNodeFactory f,WorkMemory m){
		this.f=f;
		t=f.getTrigonometry(); 
		if (t==null){
			throw new RuntimeException("========"); 
		}
		wm=m; 
	}
	public static final void setInfo(FFTNode node,boolean isReady,int from, int step, int to,int size,short type,int order,FFTNode parent){
		node.from=from; 
		node.step=step;
		node.to=to;
		node.size=size;
		node.nodeType=type;
		node.order=order; 
		if (node.size==FFTNode.MIN_SIZE){
			node.isReady=true; 
		}else {
			node.isReady=isReady; 
		}
		node.parent=parent; 
	}

	private final void setInfo(boolean isReady,int from, int step, int to,int size,short type,int order,FFTNode parent){
		this.from=from; 
		this.step=step;
		this.to=to;
		this.size=size;
		this.nodeType=type;
		this.order=order; 
		if (this.size==FFTNode.MIN_SIZE){
			this.isReady=true; 
		}else {
			this.isReady=isReady; 
		}
		this.parent=parent; 
	}
	public final boolean isReady(){
		return isReady; 
	}
	
	public String toString(){
		return from+"->"+(to-1); 
	}
	private final void process(float[] real, float[] image,int firstN){
		float right_re;  
		float right_im;
		float left_re;  
		float left_im; 
        float wk_re;  
        float wk_im; 

        int offset_leftChild=from;
    	int offset_rightChild=from+step; 
    	int step_child=step<<1; 
    	int half_size=size>>1; //8  size=16, step=1, half_size=8; 
		int window=Math.min(half_size,firstN); //Math.min(half_size, 16);    	
    	int offset=from;
    	//System.out.println("=======*="+size+"=*===========");
    	/* [0 1 2 3 4  5  6  7   8 9 10 11 12 13 14 15]
    	 * [0 2 4 6 8 10 12 14] [1 3  5  7  9 11 13 15]
    	 *         ___________________________V_________________________
    	 * 		  k=0      1      2       3      4       5     6       7   
    	 * left:    0      2      4       6      8       10    12      14 
    	 * right:   1      3      5       7      9       11    13      15
    	 * parent: (0,8) (1,9)  (2,10)  (3,11) (4,12) (5,13) (6,14)  (7,15)  (k,k+half_size)
    	 *       2m=0            2              4               6       
    	 *      2m+1=      1              3              5              7
    	 *        m=0      0     1        1     2        2      3       3 
    	 *        q=4      5     6        7                           
    	 *
    	 *     k=(0,4), read 0,1,8,9, update 0,8, keeps 4,12     (1,9)  k=1
    	 *     k=(2,6), read 4,5,12,13 update 4,12, keeps 6,14   (5,13) k=5; 
    	 *     
    	 *     k=(3,7), read 6,7,14,15 update 6,14,7,15          leaves null; 
    	 *     
    	 *     k=(1,5), read 2,3,10,11 update 1,9,5,13. ( keeps 5,13)
    	 *      
    	 *     k           read     2k,2k+1                      
    	 *                 update   k,         (k+half_size).
    	 *                 conflict (k+half_size)/2
    	 *                 do (k+half_size)/2 
    	 *                 update k+half_size  
    	 *                   
    	 *     for k is odd
    	 *     k           read     2k,2k+1                      
    	 *                 update   k,         k+half_size.
    	 *                 conflict floor(k+half_size)/2  
                  
    	 *     
    	 *     (k,k+quad_size) read          (2k,2k+1,2k+half_size,2k+half_size+1)
    	 *                     update        (k,k+half_size), 
    	 *                     keeps         (k+quad_size,k+quad_size+half_size).
    	 *                     do            (k,k+half_size)
    	 *                     corresponds:  ((k+quad_size)/2, (k+quad_size)/2+quad_size)
    	 *                     
    	 *     
    	 *     continue it till (k+quad_size) is not a even any more. 
    	 *                     
    	 *                     m  
    	 *     left quad_size=2            
    	 *                           m-1
    	 *     k=0, (k+quad_size)/2=2
    	 *         m      m-1     m-1        m-2      m-2      m-2
    	 *     (0,2  )=>(2   , 3*2    )=>(3*2    , 3*2    + 4*2    )
    	 *                 p         m-p      p+1        m-p            
    	 *           ==>((2    -1)* 2    ,  (2   -1)  * 2    )
    	 *                     m        m+1
    	 *           =...=> ((2  -1), (2    - 1))
    	 *                                         m-p
    	 *                                        2
    	 *           m-1      m-2       p      m-p     p+1      m-p+1
    	 *    k=0,  2    , 3*2        (2  -1)*2    , (2    -1 )2
    	 *       
    	 *     m             m+1  m+1                 m+1   m      m 
    	 * (0,2  ) read 0,1,2   ,2    +1 , impact (0,2   , 2  , 3*2  )
    	 *                        m+1
    	 *            update (0, 2    )
    	 *                     m      m
    	 *            keep   (2  , 3*2  )
    	 *                        m+1                                             m+1
    	 *            leave  (1, 2   +1 ) = (1, half_size+1) do 1 will change (1,2   +1).
    	 *            
    	 *    p         m-p      p+1        m-p            
    	 * ((2    -1)* 2    ,  (2   -1)  * 2    )
    	 *                  p       m-p+1   p     m-p+1      p       m-p+1   p      m-p+1
    	 *         read   (2   -1)*2,     (2  -)*2    + 1, (2   -1)*2  ,   (2  -1)*2   + 1
    	 *                  p         m-p      p+1        m-p    m+1
    	 *       impact   (2    -1)* 2    ,  (2   -1)  * 2    + 2
    	 *                  p+1       m-p     p+1         m-p    m+1
    	 *                (2    -1)* 2    ,  (2   -1)  * 2    + 2  
    	 *     
    	 *     it is a (m+1) -length loop;
    	 *     
    	 *     m=3, half_size=16, quad_size=8 
    	 *     0  1  2  3  4  5  6  7  8  9   10 11 12 13 14 15
    	 *   l:0  2  4  6  8  10 12 14 16 18  20 22 24 26 28 30 
    	 *   r:1  3  5  7  9  11 13 15 17 19  21 23 25 27 29 31
    	 *   p 0  1  2  3  4  5   6  7  8  9  10 11 12 13 14 15
    	 *   p 16 17 18 19 20 21  22 23 24 25 26 27 28 29 30 31
    	 *     example: (0,8)=>(4,12)=>(6,14)=>(7,13) 
    	 *              
    	 *                m+1
    	 *     half_size=2       means 
    	 *           
    	 *     
    	 *     the above mentioned process end when 
    	 *     
    	 * left:   from + k*step_child   =from + 2k*step; 
    	 * right:  from+step+k*step_child=from+(2k+1)*step; 
    	 * parent: from + k*step, from+k*step+half_size*step;
    	 *         from + k*step< from+k*step_child,
    	 *           
    	 *         from+k*step+half_size*step=from+2q*step
    	 *      or   
    	 *         from+k*step+half_size*step=from+(2q+1)*step
    	 *  namely       
    	 *           (k+half_size)=2q or (k+half_size)=2q+1; 
    	 *           q(k)=ceiling([k+half_size]/2);  half_size is always even;
    	 *           computer k will change k itself and q(k), involve 4 elements;
    	 *           2 of them can be updated, but (k+half_size/2, q(k+half_size/2))
    	 *           is not updatable until h has been computed, where h reads 
    	 *           2*h, 2*h+1, 2h=k+half_size/2. 
    	 *           
    	 */
		for (int k = 0; k<window; k++) {
			Complex e_kN=t.get(k, size, order);			
			right_re=real[offset_rightChild]; 
			right_im=image[offset_rightChild]; 
			    			
			wk_re=(float)(right_re*e_kN.re-right_im*e_kN.im); 
			wk_im=(float)(right_re*e_kN.im+right_im*e_kN.re);
			    			
			left_re=real[offset_leftChild]; 
			left_im=image[offset_leftChild]; 
			real[offset]=left_re+wk_re;
			image[offset]=left_im+wk_im;
			
			int dual=offset+0;  
			real[dual]=left_re+wk_re;
			image[dual]=left_im+wk_im;
			
			offset_leftChild+=step_child;
			offset_rightChild+=step_child;
			offset+=step; 
		}
	}

	private final void process99(float[] real, float[] image,int firstN){
		float right_re;  
		float right_im;
		float left_re;  
		float left_im; 
        float wk_re;  
        float wk_im; 

        int offset_leftChild=from;
    	int third;
    	int offset_rightChild=from+step; 
    	int half_size=size>>1; //8
    	int quad_size=half_size>>1; //4 
    	int step_child=step<<1; 
		int window=Math.min(quad_size,firstN); //Math.min(half_size, 16);
    	float sin,cos;  
    	int shift=step_child*quad_size; //
    	
    	//System.out.println("=======*="+size+"=*===========");
    	/* [0 1 2 3 4  5  6  7   8 9 10 11 12 13 14 15]
    	 * [0 2 4 6 8 10 12 14] [1 3  5  7  9 11 13 15]
    	 *         ___________________________V_________________________
    	 * 		  k=0      1      2       3      4       5    6       7 
    	 * left:    0      2      4       6      8      10    12      14 
    	 * right:   1      3      5       7      9      11    13      15
    	 * parent: (0,8) (1,9)  (2,10)  (3,11) (4,12) (5,13) (6,14)  (7,15)
    	 *            ^     ^       ^       ^      ^      ^      ^                                   
    	 *                      (*)
    	 *                  (6   ,   14)
    	 *                  (12  ,   13)
    	 *               (4,12)     (5,13)  
    	 *               (8, 9)     (10,11)
    	 *            (0,8) (1,9) (2,10) (3,11)
    	 *            
    	 * left:   from + k*step_child   =from + 2k*step; 
    	 * right:  from+step+k*step_child=from+(2k+1)*step; 
    	 * parent: from + k*step, from+k*step+half_size*step;
    	 *         from + k*step< from+k*step_child,
    	 *           
    	 *         from+k*step+half_size*step=from+2q*step
    	 *      or   
    	 *         from+k*step+half_size*step=from+(2q+1)*step
    	 *  namely       
    	 *           (k+half_size)=2q or (k+half_size)=2q+1; 
    	 *           q=ceiling([k+half_size]/2);  half_size is always even;
    	 *            
    	 *           let k=2m, 2m+1; 
    	 *           q=m+half_size/2 or m+1+half_size/2 <half_size 
    	 *           m<half_size/2=size/4; 
    	 *           for (m=0; m<size/4; m+=2) {
    	 *               k=2m;  
    	 *               compute for 2m*step and 2m*step+half_size*step; 
    	 *               k=2m+1; 
    	 *               compute for (2m+1)*step and (2m+1)*step+half_size*step;
    	 *               conflict with q=m+half_size/2; 
    	 *           }         
    	 */
		for (int k = 0; k<window; k++) {
			Complex e_basekN=t.getBase(k, size, order);
			cos=(float)e_basekN.re; 
			sin=(float)e_basekN.im; 
			
			// quadrant 1; 
			right_re=real[offset_rightChild]; 
			right_im=image[offset_rightChild]; 
			    			
			wk_re=(float)(right_re*cos-right_im*sin); 
			wk_im=(float)(right_re*sin+right_im*cos);
			    			
			left_re=real[offset_leftChild]; 
			left_im=image[offset_leftChild];
			// corresponding to offset,
			// parent kth-component overwrite left child's kth component;  
			wm.real[k]=left_re+wk_re;  
			wm.image[k]=left_im+wk_im;
			
			// quadrant 3;
			
			
			
			third=k+half_size;
			wm.real[third]=left_re-wk_re;
			wm.image[third]=left_im-wk_im;
			
			/*
			
			System.out.println("===================="); 
			System.out.println("par 1)  "+k+","+third +"/ size:"+half_size); 
			System.out.println("        "+offset_leftChild+","+offset_rightChild +"/ size:"+half_size); 
			
			*/
			
			// quadrant 2; k'=k+N/4, shift=N/4; 
			
			int k2=k+quad_size;
			if (k2<firstN){			
				right_re=real[offset_rightChild+shift]; 
				right_im=image[offset_rightChild+shift]; 

				wk_re=(float)(right_re*sin+right_im*cos); 
				wk_im=(float)(-right_re*cos+right_im*sin);
			
				left_re=real[offset_leftChild+shift]; 
				left_im=image[offset_leftChild+shift]; 
			
				wm.real[k2]=left_re+wk_re;
				wm.image[k2]=left_im+wk_im;
			
				// quadrant 4;
			
				third=k+half_size+quad_size;
				wm.real[third]=left_re-wk_re;
				wm.image[third]=left_im-wk_im;
			
				/*
				System.out.println("par 2)  "+(k+quad_size)+","+third +"/ size:"+half_size+"/"+quad_size);
				System.out.println("        "+(offset_leftChild+shift)+","+(offset_rightChild+shift) +"/ size:"+half_size);
				 */
			}
			offset_leftChild+=step_child;
			offset_rightChild+=step_child;
									
		}
		int offset=from;	
		
		window=Math.min(half_size,firstN)<<1;
		for (int k = 0; k<window; k++) {				
			real[offset]=wm.real[k];
			image[offset]=wm.image[k];
			offset+=step;				
		}
		
							
	}
	private final void process2(float[] real, float[] image){
		float right_re;  
		float right_im;
		float left_re;  
		float left_im; 
        float wk_re;  
        float wk_im; 

        int offset_leftChild=from;
    	int dual; 
    	int offset_rightChild=from+step; 
    	int half_size=size>>1;
    	int step_child=step<<1; 
		int window=Math.min(half_size,16); //Math.min(half_size, 16);
		for (int k = 0; k<window; k++) {
			Complex e_kN=t.get(k, size, order);
			
			right_re=real[offset_rightChild]; 
			right_im=image[offset_rightChild]; 
			    			
			wk_re=(float)(right_re*e_kN.re-right_im*e_kN.im); 
			wk_im=(float)(right_re*e_kN.im+right_im*e_kN.re);
			    			
			left_re=real[offset_leftChild]; 
			left_im=image[offset_leftChild]; 
			wm.real[k]=left_re+wk_re;
			wm.image[k]=left_im+wk_im;
			
			dual=k+half_size;
			wm.real[dual]=left_re-wk_re;
			wm.image[dual]=left_im-wk_im;
			offset_leftChild+=step_child;
			offset_rightChild+=step_child;
			
		}
		int m=half_size*step;
		int offset=from;
		int pos; 
		for (int k = 0; k<window; k++) {				
			real[offset]=wm.real[k];
			image[offset]=wm.image[k];
			dual=offset+m; 
			pos=k+half_size; 
			real[dual]=wm.real[pos]; 
			image[dual]=wm.image[pos]; 
			offset+=step;				
		}		
	}
	public final void compute(boolean[] x, float[] real, float[] image,int firstN){
		//System.out.println("compute "+from+"->"+(to-1)+" size:"+size);
		if (this.nodeType==Node_RIGHT){
			this.parent.isReady=true; 
		}
		float right_re;  
		float right_im;
		float left_re;  
		float left_im; 
        float wk_re;  
        float wk_im;
        int i,k,index; 
        switch(size){
        case 1: 
        	return;
        case 2:        	 
        	left_re=x[from]?1:0; 
        	right_re=x[from+step]?1:0;
        	real[from]=left_re+right_re;  
        	image[from]=0; 
        	real[from+step]=left_re-right_re;
        	image[from+step]=0;        	
        	return ;
        case MIN_SIZE:
        	index=0; 
        	for (i=from,k=0; i<to; i+=step,k++){
        		if (x[i]){
        			index+=(1<<(BinaryFFTCache.WIDTH-k-1)); 
        		}
        	}
        	//System.out.println("index:"+index); 
        	Complex[] cached=BinaryFFTCache.items[index].ffted; 
        	for (i=from,k=0; i<to; i+=step,k++){
        		real[i]=(float)cached[k].re; 
        		image[i]=(float)cached[k].im; 
        	}
        	return ; 
        default:
        	process(real,image,firstN); 
        }
	}
	/*
	public void compute(boolean[] x, float[] real, float[] image){
		// combining two piece together; 
		if (this.nodeType==Node_RIGHT){
			this.parent.isReady=true; 
		}
		//System.out.println("compute "+from+"->"+(to-1)+" size:"+size);
		Trigonometry t=f.getTrigonometry();
		float right_re;  
		float right_im;
		float left_re;  
		float left_im; 
        float wk_re;  
        float wk_im; 

        switch(size){
        case 1:
        	return ; 
        case 2:
        	left_re=x[from]?1:0; 
        	right_re=x[from+step]?1:0;    
        	// e_kN.re=1; e_kN.im=0;
			//wk_re=even_re; 
			//wk_im=0; 
        	real[from+step]=left_re-right_re;
        	image[from+step]=0; 
        	
        	real[from]=left_re+right_re;  
        	image[from]=0; 
        	return ; 
        default:
            int offset_leftChild=from;
            int dual; 
            int offset_rightChild=from+step; 
			int half_size=size>>1;
			int step_child=step<<1; 
			int window=half_size; //Math.min(half_size, 16);
    		for (int k = 0; k<window; k++) {
    			right_re=real[offset_rightChild]; 
    			right_im=image[offset_rightChild]; 
    			Complex e_kN=t.get(k, size, order);    			
    			wk_re=(float)(right_re*e_kN.re-right_im*e_kN.im); 
    			wk_im=(float)(right_re*e_kN.im+right_im*e_kN.re);
    			
    			System.out.println("====="+k+"======"); 
    			System.out.println(k+" wk:"+wk_re+","+wk_im +"/"+half_size+" angle:"+e_kN);
    			System.out.println(right_re+","+right_im);
    			System.out.println("offset_child:"+offset_leftChild+","+(offset_rightChild)); 
    			System.out.println("-----------");
    			
    			left_re=real[offset_leftChild]; 
    			left_im=image[offset_leftChild]; 
    			wm.real[k]=left_re+wk_re;
    			wm.image[k]=left_im+wk_im;
    			//real[offset]=real[offset_leftChild]+wk_re; 
    			//image[offset]=image[offset_leftChild]+wk_im;
    			
    			dual=k+half_size;
    			wm.real[dual]=left_re-wk_re;
    			wm.image[dual]=left_im-wk_im;
    			//real[dual]=real[offset_leftChild]-wk_re;   
    			//image[dual]=image[offset_leftChild]-wk_im;      			
    			//offset+=step;  
    			offset_leftChild+=step_child;
    			offset_rightChild+=step_child; 
    		}
    		int m=half_size*step;
    		int offset=from;
    		int pos; 
			for (int k = 0; k<window; k++) {
				real[offset]=wm.real[k];
				image[offset]=wm.image[k];
				dual=offset+m; 
				pos=k+half_size; 
				real[dual]=wm.real[pos]; 
				image[dual]=wm.image[pos]; 
				offset+=step; 
			}
        }
	}
	*/
	/*
	public int createChildNodes(FFTNode[] childNodes){
		int step_child=step<<1; 
		int size_child=size>>1; 
		int order_child=order-1; 
		if (size>FFTNode.MIN_SIZE){
			childNodes[0]=f.createFFTNode(from+step,step_child,to,size_child,Node_RIGHT,order_child,this); 			 
			childNodes[1]=f.createFFTNode(from,step_child,to-step,size_child,Node_LEFT,order_child,this);
			return 2; 
		}else {
			return 0;  
		}
	}
	*/
	public final int createChildNodes(FFTNode[] childNodes){
		if (size>FFTNode.MIN_SIZE){
			int step_child=step<<1; 
			int size_child=size>>1; 
			int order_child=order-1;
			boolean isReady_child=size==(FFTNode.MIN_SIZE<<1);
			
			f.create2FFTNodes(childNodes);
			FFTNode right=childNodes[0];
			right.isReady=isReady_child; 
			right.from=from+step; 
			right.step=step_child; 
			right.to=to;
			right.size=size_child;
			right.nodeType=Node_RIGHT;
			right.order=order_child;
			right.parent=this;
			
			FFTNode left=childNodes[1]; 
			left.isReady=isReady_child;
			left.from=from;
			left.step=step_child;
			left.to=to-step;
			left.size=size_child;
			left.nodeType=Node_LEFT;
			left.order=order_child;
			left.parent=this; 
			
			return 2; 
		}else {
			return 0;  
		}
	}
	public static int[] bitReverse(int[] x){
		int j=1;
		int n=x.length; 
	    for (int i=1;i<n;i++) { 
	        if (j > i) {
	            //swap the real part
	        	int xj=x[j];
	        	int xi=x[i]; 
	        	x[j]=xi; 
	        	x[i]=xj; 
	        }
	        int m=n;
	        while (m >= 2 && j > m) {
	            j -= m;
	            m = m/2;
	        }
	        j += m;
	    }
	    return x; 
	}
	public static int[] bitReverse(int[] x,final int bit){
		int rev,tmp1,tmp2,maskl,maskh,m,n,shift;
		rev = 0;
		int N=1<<bit;
		int[] br=new int[N]; 
		for (n=0;n<N;n++)
		 {
		   for (m=0;m<(bit/2.0)+0.5;m++){
		        shift = (bit-((m*2)+1));
		        maskl = 1<<m;
		        tmp1 = (n & maskl) << shift;
		                      maskh = N/2>>m;
		        tmp2 = (n & maskh) >> shift;
		       rev = rev | tmp1 | tmp2;
		    }
		      br[n] = rev ;
		      rev = 0;
		 }
		return br; 
    }
	public static void main(String[] args){
		int order=4; 
		int dim=1<<order;
		int[] x=new int[dim]; 
		for (int i=0; i<dim; i++){
			x[i]=i; 
		}
		int[] br=bitReverse(x,order); 
		for (int i=0; i<dim; i++){
			System.out.println(i+")"+br[i]); 
		}
		//System.out.println(128>>1); 
	}
}
